The present invention relates to scaling (i.e., enlarging or reducing) images. It finds particular application in conjunction with scaling antialiased original color images to prepare them for display on hard-copy or soft-copy and will be described with particular reference thereto. It will be appreciated, however, that the invention is also amenable to other like applications.
The use of graphics in computer and communication applications is very widespread and is becoming increasingly prevalent. A computing device often transmits a document including graphical data to a printing device using a page description language. Page description languages (e.g., the PostScript(copyright) language) include interpretive programming commands useful for implementing powerful graphics capabilities. When transmitted via a page description language, graphical data is typically converted into a raster image file. Printing devices then include electronics and software for making marks on paper corresponding to positions in the raster image file where the image values so indicate.
Page description language interpreters may include means for printing antialiased images. In the context of gray-scale raster data, antialiasing refers to introducing intermediate intensity levels along edges of the object for smoothing jagged lines in lower resolution images. Similarly, in the context of color raster data, antialiasing refers to introducing intermediate colors along the edges of objects to achieve the same effect in lower resolution color images.
In general, the cost of computing power necessary for manipulating data is at least proportional to the amount of data to be manipulated. Therefore, it is often cheaper to manipulate data for lower resolution images. When it becomes desirable to print the image stored using low-resolution data, the data must then be scaled up to a higher resolution. In this manner, a high-resolution image is produced using less computing power than would otherwise be required. Similarly, the image is transmitted using substantially less transmission bandwidth. For example, an image to be printed at 1000 square inches per minute, 600xc3x974800 spots per inch, and 1 bit per pixel, if transmitted at full resolution, requires 48 M bits per second raw bandwidth. On the other hand under the same circumstances, if the image is computed at 400 spots per inch, antialiased to 8 bits per pixel, and transmitted before scaling, the total required bandwidth is only 21 M bits per second.
Scaling up a pixel of an image included within an area having a single, constant color is relatively simple. More specifically, each pixel within the area of constant color is replaced by a group of pixels having the same color.
Scaling up pixels along edges or other geometries, on the other hand, is relatively more complicated. FIG. 1 illustrates a portion of an antialiased image 10 having dark lines 12 that are approximately 2.5 pixels thick. The lines 12 in FIG. 1 are scaled up for improved visibility and are best viewed at approximately five (5) feet for receiving a correct subjective impression. FIG. 2 illustrates a magnified view 14 of the top, left portion of FIG. 1. The edge position 16 of FIG. 2 is represented by pixels having intermediate gray-levels. When the intermediate gray-levels are halftoned, as shown in FIG. 3, the resulting appearance 20 depends strongly on where the dot center is relative to the pixel. If the image is halftoned using a typical high-addressability scheme, in which each contone input pixel is replaced with a set of binary output pixels, some of the generated halftone dots 22 are disconnected from the line 24 (see FIG. 3). Several conventional algorithms (e.g., hyperacuity and tagged antialiased imaging) exist for scaling up pixels to be halftoned.
Hyperacuity seeks to improve image quality without increasing overall resolution. Information concerning the location of where edges are to be printed is maintained with a high degree of accuracy, but without increasing the resolution of the input data. A byte-map, instead of a bit-map, is used for the desired image of text (or lineart) to be printed. Each bit position is replaced with a multi-bit byte of coded information, such as a gray value or pixel. The information contained in these multi-bit gray pixels is processed with neighboring gray pixels within the hyperacuity printer to generate an identification of where the edges should be placed. This information, in turn, is used to adjust the exposure in the printer in an optimal manner in order to produce edges that do not have a stair stepping effect. Hyperacuity printing requires a preprocessing stage for deciding when to simply halftone the image and when to treat it as line art and interpolate an edge position.
Tagged antialiased imaging involves thresholding input data into various categories of brightness. Template matching is used to determine whether the thresholded data xe2x80x9clooksxe2x80x9d like an antialiased edge. The template matching approach tags pixels along the edge to indicate whether the edge is dark on the left, the right, or top/bottom. The halftone screen is changed in accordance with which of the four (4) cases occurs (i.e., left, right, top/bottom, or none). In the left and right cases, a high-frequency screen having darkness and lightness growing from one side of the screen is used. In the top/bottom case, the screen grows from the center.
Tagged antialiased imaging is based on an assumption that edges worth rendering as antialiased are only identified by intermediate color-levels. Furthermore, neither of the methods discussed above, is capable of determining whether an edge exists or an orientation of an edge when the edge divides two regions of color that are not full (or nearly) on and off. Therefore, this information must be supplied to the hyperacuity and tagged antialiased rendering algorithms.
One approach used for generating tags for hyperacuity and tagged antialiased rendering is to threshold the data so that pixels with one neighbor having more than one threshold and one having less than another threshold must be present. Having a threshold at which the rendering technique changes invariably leads to the possibility of artifacts. First, consider a 95% black line on a sweep from white to 50% gray. At some point in the sweep, the contrast drops to a point that the rendering technique changes, leading to an artifact at this point. Second, consider a pictorial image. Only very high contrast edges in such an image will retain an acceptable appearance if rendered as lineart, or tagged to use the high frequency halftone. If the threshold is too low, far too many pixels within an image fit the criterion and, therefore, use the high-frequency halftone. Even synthetic data may not switch smoothly between the methods. A line at certain angles may have pixels that appear to meet the criterion, whereas elsewhere on the same line there are pixels that do not. FIG. 3 illustrates that a variety of gray-levels result in such situations.
As illustrated in FIG. 4, a partial dotting 26 preserves an edge 28 when a xe2x80x9ccleanxe2x80x9d edge is between first and second gray-levels 30, 32, respectively. Despite the fact that the edge 28 is not between black and white, it is preserved as well as can be achieved without changing the intensity along the edge 28. This results as a natural consequence of halftoning an edge between two gray levels if the edge is at the same resolution as the halftone dot.
Another conventional method for transforming a pixel from low-resolution to high-resolution looks at a window around the pixel. Patterns are identified within the pixels in the window. The patterns are compared to known samples at both 300 spots per inch (xe2x80x9cspixe2x80x9d) and 600 spi. There are several drawbacks with this method. For example, the original image may contain patterns that are not recognized. Furthermore, the patterns viewed at 300 spi may equally translate to two (2) different objects at 600 spi. Also, in order to be able to accurately identify patterns, the number of pixels within the window may need to be relatively large, which requires more memory. Furthermore, a relatively large look-up table, having significantly more gates, is required to store the different patterns. Another disadvantage of such a method as commonly practiced is that it involves the use of thresholding and, therefore, is not capable of handling edges between any two (2) gray-levels.
A previous scaling algorithm uses a 3xc3x973 context and includes 1) determining whether an edge is present, 2) if an edge is present, determining an edge angle and intercept, and 3) replacing the pixel at the center using a lookup table if an edge is present, or interpolation if an edge is not present. More specifically, the 3xc3x973 scaling algorithm classifies pixels as to whether they are edges or interiors and, consequently, whether they should be halftoned or provided with a high-definition edge.
The 3xc3x973 classifier, which has been used with Hyperacuity, determines if an edge appears to pass through a center pixel of a 3xc3x973 neighborhood. If an edge is found in the center pixel, the orientation and colors of the two (2) regions it separates are determined. A difference (dX) between sums of pixels in the first and last rows and a difference (dY) between the sums of the pixels in the first and last columns are calculated. Then, a determination is made whether an edge exists as a function of dX, dY, and the pixel colors.
The notion behind the 3xc3x973 context scaling is that where a clean edge exists in antialiased input, the data may be interpreted to find the precise edge location and the two (2) colors that the edge separates. This process improves the rendition of text and synthetic graphics, but is best not applied in pictorials, unless they contain such clean edges. Therefore, because false edges may cause artifacts in pictorials, and because missed edges may result in halftoned portions of antialiased text and lineart, it is important to correctly classify pixels. The 3xc3x973 scaling algorithm is relatively reliable for classifying edges in lines that are about 2 pixels or wider. However, lines that are less than about 2 pixels wide are sometimes misclassified, and edge patterns are not identified.
The present invention provides a new and improved apparatus and method which overcomes the above-referenced problems and others.
An apparatus for rendering an image includes a memory for storing display data associated with a primary neighborhood of pixels within the image. A processor, communicating with the memory, assigns tags to a pixel of interest within the primary neighborhood as a function of a plurality of edge detection analyses performed on the display data in respective sub-neighborhoods within the primary neighborhood. Each of the sub-neighborhoods includes the pixel of interest.
In accordance with one aspect of the invention, an output device, which communicates with the processor, displays the scaled up pixel of interest.
In accordance with a more limited aspect of the invention, the output device is a color printing device.
In accordance with another aspect of the invention, the processor scales up the pixel of interest within the primary neighborhood if a majority of the edge detection analyses determine that an edge is included within the respective sub-neighborhoods.
In accordance with a more limited aspect of the invention, the processor determines respective edge types in the sub-neighborhoods.
In accordance with an even more limited aspect of the invention, scaled up display data for the pixel of interest is calculated as a function of the display data associated with the sub-neighborhoods including the edge.
In accordance with another aspect of the invention, the scaled up display data for the pixel of interest is calculated as a function of a slope of the edge within the sub-neighborhood including the pixel of interest.
In accordance with another aspect of the invention, colors of the scaled up display data are determined as a function of colors within the sub-neighborhoods including the edge.
In accordance with another aspect of the invention, the primary neighborhood is a 5xc3x975 neighborhood of pixels. Each of the sub-neighborhoods is a 3xc3x973 neighborhood of pixels, and the processor performs 3 edge detection analyses.
In accordance with another aspect of the invention, the tags identify whether an edge, along with an associated orientation of the edge, is present within the pixel of interest.
One advantage of the present invention is that it is capable of classifying lines that are less than about 2 pixels wide for identifying edge patterns.
Another advantage of the present invention is that it is capable of handling edges between any two (2) gray-levels.
Still further advantages of the present invention will become apparent to those of ordinary skill in the art upon reading and understanding the following detailed description of the preferred embodiments.